package com.github.yangyishe.p100;

/**
 * 53. 最大子数组和
 * https://leetcode.cn/problems/maximum-subarray/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 *
 * 子数组 是数组中的一个连续部分。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 * 示例 2：
 *
 * 输入：nums = [1]
 * 输出：1
 * 示例 3：
 *
 * 输入：nums = [5,4,-1,7,8]
 * 输出：23
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * -104 <= nums[i] <= 104
 *
 *
 * 进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
 */
public class Problem53 {
    public static void main(String[] args) {
        int[] nums=new int[]{-10,-1};

        Problem53 problem53 = new Problem53();
        int max = problem53.maxSubArray(nums);
        System.out.println("max = " + max);

    }

    /**
     *
     * 思考思路:
     * 1. 如果数组有1个元素, 则最大和maxSum(0)=Math.max(0,nums[0])
     * 2. 如果数组有2个元素, 则最大和maxSum(0,1)=maxSum(0)+maxSum(1)=Math.max(0,nums[0])+Math.max(0,nums[1])
     * 3. 如果数组有3个元素, 则最大和maxSum(0,2)=Math.max(maxSum(0,1)+maxSum(2),maxSum(0)+maxSum(1,2))
     *
     *
     * 实现思路:
     * 记录两个数据:
     * 1. 遍历历史最大和
     * 2. 紧邻当前元素左侧最大和. 遍历时只要该值小于0,就一直累加(当前元素);如果小于0,则取负值.每次维护时, 也需要维护历史最大和.
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int max=0;
        int nbMax=0;
        int maxEach=nums[0];


        for(int num:nums){
            if(nbMax>-num){
                nbMax+=num;
                if(num>0){
                    max=Math.max(max,nbMax);
                }
            }else{
                nbMax=0;
            }
            maxEach=Math.max(maxEach,num);
        }

        return maxEach>0?max:maxEach;
    }
}
